package LinkedList;/**


/**
 * @author TangYuan
 * @className MyLinkedList
 * @description TODO 单向链表，新增/删除节点
 * @date 2020/5/14 20:36
 */
public class MyLinkedList {

    //链表头节点
    private Node head;

    //链表实际长度
    private int size;

    private Node endNode;

    /**
     * 在链表指定位置插入数据
     *
     * @param index 指定插入位置
     * @param data  插入的值
     */
    //分别在一个空链表/链表头部/链表尾部/链表中间插入一个节点
    private void insertNode(int index, int data) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }

        Node node = new Node(data);
        //空链表
        if (size == 0) {
            head = node;
            endNode = node;
        } else if (index == 0) {
            //插入头节点
            head = node;
            node.next = head;
        } else if (index == size) {
            //插入尾部
            endNode.next = node;
            endNode = node;
        } else {
            //中间插入
            Node prevNode = get(index - 1);
            node.next = prevNode.next;
            prevNode.next = node;
        }
        size++;
    }

    /**
     * 删除指定为位置节点
     * @param index
     */
    public void deleteNode(int index) throws Exception {
        if(index<0 || index>size){
            throw new NullPointerException("超出当前链表范围");
        }
        Node temp = null;
        //删除头部节点
        if(index == 0){
            temp = head;
            head  = head.next;
        }else if(index == size-1){
            //删除尾节点
            endNode  = null;
            Node prevNode = get(index-1);
            prevNode.next = null;
            endNode = prevNode;
        }else {
            //删除中间指定位置节点
            Node prevNode = get(index-1);
            Node nextNode = prevNode.next.next;
            prevNode.next = null;
            prevNode.next = nextNode;

        }
        size--;
    }
    

    /**
     * 获取指定位置节点
     *
     * @param index 指定位置
     * @return 链表指定位置节点
     */
    public Node get(int index) throws Exception {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表范围");
        }
        Node temp = head;

        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }


    /**
     * 遍历整个链表输出节点的值
     */
    private void output() {
        Node temp = head;
        while (null != temp) {
            System.out.print(temp.datas + ",");
            temp = temp.next;
        }


    }


    public static void main(String[] args) throws Exception {
//        //尾部插入节点
        MyLinkedList endNodeLinkedList = new MyLinkedList();
        endNodeLinkedList.insertNode(0, 5);
        endNodeLinkedList.insertNode(1, 6);
        endNodeLinkedList.insertNode(2, 2);
        endNodeLinkedList.insertNode(3, 9);
        endNodeLinkedList.output();

        //空链表插入节点
        MyLinkedList emptyLinkedList = new MyLinkedList();
        emptyLinkedList.insertNode(0, 1);
        emptyLinkedList.output();

        //已知链表中间插入一个节点
        MyLinkedList midLinkedList = new MyLinkedList();
        midLinkedList.insertNode(0, 3);
        midLinkedList.insertNode(1, 4);
        midLinkedList.insertNode(2, 5);
        midLinkedList.insertNode(3, 6);
        midLinkedList.insertNode(2, 9);
        midLinkedList.output();

        //删除指定位置节点

        MyLinkedList delteLinkedList  = new MyLinkedList();
        delteLinkedList.insertNode(0,1);
        delteLinkedList.insertNode(1,5);
        delteLinkedList.insertNode(2,6);
        delteLinkedList.insertNode(3,7);
        delteLinkedList.insertNode(4,8);
        delteLinkedList.insertNode(5,9);
        delteLinkedList.insertNode(6,10);

        //删除头节点
        delteLinkedList.deleteNode(0);
        delteLinkedList.output();
        //删除尾部节点
        delteLinkedList.deleteNode(delteLinkedList.size-1);
        delteLinkedList.output();
//        //删除中间指定位置节点
        delteLinkedList.deleteNode(3);
        delteLinkedList.output();
    }
}
